package 链表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * TODO
 * <p>
 * 1、
 * <p/>
 * User: zhaixiaolong Date:2024/1/3 15:59 ProjectName: algorithm Version: V1
 */
public class 设计链表 {

    public static void main(String[] args) {
        MyLinked linkedList = new MyLinked();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        System.out.println(linkedList.toString());
        linkedList.addAtIndex(1, 2);   //链表变为1-> 2-> 3
        System.out.println(linkedList.toString());
        System.out.println(linkedList.get(1).value);            //返回2
        linkedList.deleteAtIndex(1);  //现在链表是1-> 3
        System.out.println(linkedList.toString());
        System.out.println(linkedList.get(1).value);            //返回3
    }

    static class MyLinked {

        int size;

        Node head;

        public MyLinked() {
            size = 0;
        }

        public void addAtHead(int value) {
            Node newHead = new Node();
            newHead.value = value;
            if (head == null) {
                head = newHead;
                size = 1;
            } else {
                newHead.next = head;
                head = newHead;
                size++;
            }
        }

        public void addAtTail(int value) {
            Node newNode = new Node();
            newNode.value = value;
            if (head == null) {
                head = newNode;
            } else {
                Node temp = head;
                while (temp.next != null) {
                    temp = temp.next;
                }
                temp.next = newNode;
            }

            size++;
        }

        public void addAtIndex(int index, int value) {

            if (index <= 0) {
                addAtHead(value);
            } else if (index > size) {
                return;
            } else if (index == size) {
                addAtTail(value);
            } else {
                Node newNode = new Node();
                newNode.value = value;
                // 找到替换节点前一个
                Node pre = head;
                while (index != 1) {
                    pre = pre.next;
                    index--;
                }
                // 插入
                newNode.next = pre.next;
                pre.next = newNode;
                size++;
            }
        }

        public Node get(int index) {
            if (index < 0 || index > size - 1) {
                return null;
            }
            int startIndex = 0;
            Node curr = head;
            while (startIndex < index) {
                startIndex++;
                curr = curr.next;
            }
            return curr;
        }

        public void deleteAtIndex(int index) {
            if (size == 0 || index < 0 || index > size - 1) {
                return;
            }
            if (index == 0) {
                head = head.next;
            } else {
                // 找到替换节点前一个
                Node pre = head;
                while (index != 1) {
                    pre = pre.next;
                    index--;
                }
                pre.next = pre.next.next;
            }
            size--;
        }

        @Override
        public String toString() {
            Node temp = head;
            List<Integer> values = new ArrayList<>();
            while (temp != null) {
                values.add(temp.value);
                temp = temp.next;
            }

            return "MyLinked{" +
                    "size=" + size +
                    ", linked: " + Arrays.toString(values.toArray()) +
                    '}';
        }
    }
}
